package com.issc.zq;

import java.util.Scanner;
/**
 * Created by Administrator on 2017/8/15.
 * 理解归并算法前：先要有递归（条件判断调用自身）和堆栈（先进后出）的思想概念
 * 归并算法思想：step1：先分治，分到数组每个元素有left、right同时指向他为止
 *
 *               step2:将两个有序的数组序列整合成一个有序序列
 *
 */
public class MergeMain {
    //分治
    public static void mergeSort(int[] arry1,int left,int right,int []arry2){
        //由于递归，在此处new一个arry2也是对空间的一个浪费
        //int [] arry2 = new int[arry1.length];
        if(left < right) {
            //相当于将arry1数组一直分割到原子级别，实质上只是left和right都指向数组中的一个元素
            int mid = (left + right) / 2;
            //左分支的不断分割
            mergeSort(arry1,left,mid,arry2);
            //右分支不断分割
            mergeSort(arry1,mid+1,right,arry2);
            //开始由堆栈顶开始弹出的left和right进行整合数组
            mergeArry(arry1,left,mid ,right,arry2);
        }
    }
    //合并算法
    public static void mergeArry(int [] arry1,int left , int mid , int right,int []arry2 ){
        int arry2_left = left ;                         //缓冲数组的第一个元素的索引
        int center = mid + 1;                           //右边数组第一个数的索引
        int tmp = left;                                 //左边数组第一个数的索引，用于复原copy数组arry2到arry1
        // int arry2[] = new int [arry1.length];
        //控制两个左右分支数组一个遍历完就退出
        //实现把两个有序的数组序列整合成一个有序的序列（实质只有一个数组arry1，分为若干左右分支，然后整合）
        while(left <= mid && center <= right) {
            if (arry1[left]>arry1[center]){
                arry2[arry2_left] = arry1[center];
                ++arry2_left;
                ++center;
            }
            else
            {
                arry2[arry2_left] = arry1[left];
                ++arry2_left;
                ++left;
            }
        }
        //把左分支剩余的部分放入arry2后面；
        while(left <= mid){
            arry2[arry2_left] = arry1[left];
            ++arry2_left;
            ++left;
        }
        //处理右分支剩余数据
        while(center <= right){
            arry2[arry2_left] = arry1[center];
            ++arry2_left;
            ++center;
        }
        //将arry2的依次放回arry1数组中，涉及成员和局部变量的关系
        while(tmp <= right){
            arry1[tmp] = arry2[tmp];
            ++tmp;
        }
    }

    public static void main(String[] args) {
        while (2 > 1) {
            System.out.println();
            System.out.println("\t\t\t" + "1、数组长度为8");
            System.out.println("\t\t\t" + "2、数组长度为4（主要用于开发过程中，断点单步调试观察数组元素变化！）");
            System.out.println("请输入测试用例号：");
            Scanner input = new Scanner(System.in);
            int caseNum = input.nextInt();
            switch (caseNum) {
                case 1:
                    int[] arry1 = new int[]{23, 6, 12, 45, 67, 89, 4, 9};
                    //对空间的优化，先new好一个int []arry2的数组
                    int[] arry2 = new int[arry1.length];
                    mergeSort(arry1, 0, arry1.length - 1, arry2);
                    System.out.println("排序后的数列：");
                    for (int i = 0; i < arry1.length-1; ++i) {
                        System.out.print(arry1[i] + "\t");
                    }
                    System.out.println();
                    break;
                case 2:
                    int[] arry3 = new int[]{9, 8, 7, 6, 5};
                    //对空间的优化，先new好一个int []arry2的数组
                    int[] arry4 = new int[arry3.length];
                    mergeSort(arry3, 0, arry3.length - 1, arry4);
                    System.out.println("排序后的数列：");
                    for (int i = 0; i < arry3.length-1; ++i) {
                        System.out.print(arry3[i] + "\t");
                    }
                    break;
                default:
            }
        }
    }
}
